SP25158 STARSBC - Star

观察样例可以发现:

  1. gcd(n,k)=1\gcd(n,k)\not=1 时,不能覆盖所有点。(恰好覆盖 ngcd(n,k)\frac{n}{\gcd(n,k)}的图)

  2. kknkn-k 是同一种方案。

所以答案为 φ(n)2\frac{\varphi(n)}2{}

#include <cstdio>

int Phi( int x ) {
    int Ans = x;
    for( int i = 2 ; 1ll * i * i <= x ; i ++ )
        if( x % i == 0 ) {
            Ans = Ans / i * ( i - 1 );
            while( x % i == 0 ) x /= i;
        }
    if( x > 1 ) Ans = Ans / x * ( x - 1 );
    return Ans;
}

int n;
int main( ) {
    while( ~scanf("%d",&n) )
        printf("%d\n", Phi( n ) / 2 );
    return 0;
}